Exploiting array manipulation habits to optimize garbage collection and type flow analysis
Identifieur interne : 000783 ( Main/Exploration ); précédent : 000782; suivant : 000784Exploiting array manipulation habits to optimize garbage collection and type flow analysis
Auteurs : Dominique Colnet [France] ; Benoît Sonntag [France]Source :
- Software: Practice and Experience [ 0038-0644 ] ; 2015-12.
English descriptors
- mix :
Abstract
A widespread practice to implement a flexible array is to consider the storage area into two parts: the used area, which is already available for read/write operations, and the supply area, which is used in case of enlargement of the array. The main purpose of the supply area is to avoid as much as possible the reallocation of the whole storage area in case of enlargement. As the supply area is not used by the application, the main idea of the paper is to convey the information to the garbage collector, making it possible to avoid completely the marking of the supply area. We also present a simple method to analyze the types of objects, which are stored in an array as well as the possible presence of NULL values within the array. This allows us to better specialize the work of the garbage collector when marking the used area, and also, by transitivity, to improve overall results for type analysis of all expressions of the source code. After introducing several abstract data types, which represent the main arrays concerned by our technique (i.e., zero or variable indexing, circular arrays and hash maps), we measure its impact during the bootstrap of two compilers whose libraries are equipped with these abstract data types. We then measure, on various software products we have not written, the frequency of certain habits of manipulation of arrays, to assess the validity of our approach. Copyright © 2014 John Wiley & Sons, Ltd.
Url:
- https://api.istex.fr/ark:/67375/WNG-BW310FTV-G/fulltext.pdf
- https://hal.archives-ouvertes.fr/hal-01116288
DOI: 10.1002/spe.2300
Affiliations:
- France
- Alsace (région administrative), Grand Est, Lorraine (région)
- Université de Lorraine, Université de Strasbourg
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003C05
- to stream Istex, to step Curation: 003B61
- to stream Istex, to step Checkpoint: 000017
- to stream Hal, to step Corpus: 002124
- to stream Hal, to step Curation: 002124
- to stream Hal, to step Checkpoint: 000D40
- to stream Main, to step Merge: 000772
- to stream Main, to step Curation: 000783
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Exploiting array manipulation habits to optimize garbage collection and type flow analysis</title>
<author><name sortKey="Colnet, Dominique" sort="Colnet, Dominique" uniqKey="Colnet D" first="Dominique" last="Colnet">Dominique Colnet</name>
</author>
<author><name sortKey="Sonntag, Benoit" sort="Sonntag, Benoit" uniqKey="Sonntag B" first="Benoît" last="Sonntag">Benoît Sonntag</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:FA7EE42DE54D9AFC6B5FA7759316126873973DF2</idno>
<date when="2015" year="2015">2015</date>
<idno type="doi">10.1002/spe.2300</idno>
<idno type="url">https://api.istex.fr/ark:/67375/WNG-BW310FTV-G/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">003C05</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003C05</idno>
<idno type="wicri:Area/Istex/Curation">003B61</idno>
<idno type="wicri:Area/Istex/Checkpoint">000017</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000017</idno>
<idno type="wicri:doubleKey">0038-0644:2015:Colnet D:exploiting:array:manipulation</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01116288</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01116288</idno>
<idno type="wicri:Area/Hal/Corpus">002124</idno>
<idno type="wicri:Area/Hal/Curation">002124</idno>
<idno type="wicri:Area/Hal/Checkpoint">000D40</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000D40</idno>
<idno type="wicri:doubleKey">0038-0644:2014:Colnet D:exploiting:array:manipulation</idno>
<idno type="wicri:Area/Main/Merge">000772</idno>
<idno type="wicri:Area/Main/Curation">000783</idno>
<idno type="wicri:Area/Main/Exploration">000783</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main">Exploiting array manipulation habits to optimize garbage collection and type flow analysis</title>
<author><name sortKey="Colnet, Dominique" sort="Colnet, Dominique" uniqKey="Colnet D" first="Dominique" last="Colnet">Dominique Colnet</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>Université de Lorraine, LORIA, Villers‐Lès‐Nancy, F‐54600</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
<affiliation></affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Sonntag, Benoit" sort="Sonntag, Benoit" uniqKey="Sonntag B" first="Benoît" last="Sonntag">Benoît Sonntag</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>Université de Strasbourg, LSIIT, Illkirch, F‐67412</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Alsace (région administrative)</region>
</placeName>
<orgName type="university">Université de Strasbourg</orgName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j" type="main">Software: Practice and Experience</title>
<title level="j" type="alt">SOFTWARE: PRACTICE AND EXPERIENCE</title>
<idno type="ISSN">0038-0644</idno>
<idno type="eISSN">1097-024X</idno>
<imprint><biblScope unit="vol">45</biblScope>
<biblScope unit="issue">12</biblScope>
<biblScope unit="page" from="1639">1639</biblScope>
<biblScope unit="page" to="1657">1657</biblScope>
<biblScope unit="page-count">19</biblScope>
<date type="published" when="2015-12">2015-12</date>
</imprint>
<idno type="ISSN">0038-0644</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0038-0644</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>array</term>
<term>compiler</term>
<term>garbage collector</term>
<term>type flow</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract">A widespread practice to implement a flexible array is to consider the storage area into two parts: the used area, which is already available for read/write operations, and the supply area, which is used in case of enlargement of the array. The main purpose of the supply area is to avoid as much as possible the reallocation of the whole storage area in case of enlargement. As the supply area is not used by the application, the main idea of the paper is to convey the information to the garbage collector, making it possible to avoid completely the marking of the supply area. We also present a simple method to analyze the types of objects, which are stored in an array as well as the possible presence of NULL values within the array. This allows us to better specialize the work of the garbage collector when marking the used area, and also, by transitivity, to improve overall results for type analysis of all expressions of the source code. After introducing several abstract data types, which represent the main arrays concerned by our technique (i.e., zero or variable indexing, circular arrays and hash maps), we measure its impact during the bootstrap of two compilers whose libraries are equipped with these abstract data types. We then measure, on various software products we have not written, the frequency of certain habits of manipulation of arrays, to assess the validity of our approach. Copyright © 2014 John Wiley & Sons, Ltd.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Alsace (région administrative)</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<orgName><li>Université de Lorraine</li>
<li>Université de Strasbourg</li>
</orgName>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Colnet, Dominique" sort="Colnet, Dominique" uniqKey="Colnet D" first="Dominique" last="Colnet">Dominique Colnet</name>
</region>
<name sortKey="Colnet, Dominique" sort="Colnet, Dominique" uniqKey="Colnet D" first="Dominique" last="Colnet">Dominique Colnet</name>
<name sortKey="Sonntag, Benoit" sort="Sonntag, Benoit" uniqKey="Sonntag B" first="Benoît" last="Sonntag">Benoît Sonntag</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000783 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000783 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:FA7EE42DE54D9AFC6B5FA7759316126873973DF2 |texte= Exploiting array manipulation habits to optimize garbage collection and type flow analysis }}
This area was generated with Dilib version V0.6.33. |